La teoria degli ordini è un ramo della matematica, e in particolare dell'algebra, che studia le relazioni d'ordine tra elementi di un insieme. Un ordine è una relazione binaria che mette in relazione coppie di elementi secondo criteri di confronto, come "minore o uguale" nei numeri o "essere contenuto in" tra insiemi. Quando tale relazione è riflessiva, antisimmetrica e transitiva, si parla di ordine parziale; se invece ogni coppia di elementi è confrontabile, si ha un ordine totale. La teoria degli ordini fornisce strumenti per analizzare strutture come insiemi ordinati, reticoli e gerarchie, ed è fondamentale in ambiti che vanno dalla logica matematica all'informatica teorica.
Un poset (dall'inglese partially ordered set, "insieme parzialmente ordinato") è una coppia (P,⊑) formata da un insieme P e da una relazione di ordine parziale ⊑ definita su di esso.
Questo significa che ⊑ è:
- Riflessiva – per ogni x∈P, x⊑x;
- Antisimmetrica – se x⊑y e y⊑x, allora x=y;
- Transitiva – se x⊑y e y⊑z, allora x⊑z.
A differenza degli insiemi totalmente ordinati, in un poset non tutte le coppie di elementi devono essere confrontabili: può accadere che esistano elementi a e b per cui né a⊑b né b⊑a sono veri.
I poset possono essere rappresentati graficamente tramite diagrammi di Hasse, che omettono le frecce implicite per la transitività e mostrano solo le relazioni immediate.
Gli ordini totali sono poset in cui ogni elemento è confrontabile con qualsiasi altro elemento dell'insieme
Gli ordini discreti sono poset in cui ogni elemento è confrontabile esclusivamente con sé stesso
I flat order (ordini "piatti") sono poset in cui ciascun elemento è confrontabile con sé stesso e con un singolo elemento inferiore a tutti gli altri, definito bottom, a cui si associa il simbolo ⊥.
Domanda per il lettore: (ℕ,≤) rappresenta una poset? Totale, discreta, piatta? E (ℕ,<)? Indizio: rappresentate la relazione con il diagramma di Hasse
Interessante teorema: Qualsiasi sottoinsieme di un ordine totale è un ordine totale.
Per contesto, possiamo fare un confronto tra poset (⊑) e relazioni ben fondate (≺)
poset:
- riflessiva
- antisimmetrica
- transitiva
- ha i.d.c. (catene discendenti infinite) se non vuoto
- ⊏ può essere anche ben fondato
w.f.:
- non riflessiva (importantissimo teorema, se così fosse verrebbe fuori un ciclo, invalidando la ben fondatezza)
- antisimmetrica (altrimenti darebbe origine ad un ciclo)
- esiste la chiusura transitiva della relazione: ≺⁺
- ≺* (chiusura transitiva e riflessiva) è sempre un poset
Un poset è definito completo se ogni catena in esso ha un limite (least upper bound o l.u.b.)
Un semplice esempio è (ℕ∪{∞},≤), dotato di un elemento top, per l'appunto ∞. L'insieme dei numeri dispari ha lub ∞, l'insieme dei numeri pari ha lub ∞, e così via.
Chiaramente, ogni catena finita ha un limite (si prenda semplicemente l'ultimo elemento della catena). Se P ha solo catene finite, è completo. Ogni ordine discreto è completo, ogni flat order è completo.